//https://leetcode-cn.com/problems/shortest-palindrome/
// kmp 求解
class Solution {
public:
    string shortestPalindrome(string s) {
        if(!s.size()) return s;
        string s1 = s;
        reverse(s1.begin(),s1.end());
        if(s1 == s) return s; //原来就是回文串
        s1 = s + s1;
        string s2 = s.substr(get_next(s1,s.size()));//切下剩余部分
        reverse(s2.begin(),s2.end());
        s2 = s2 + s;
        return s2;
    }
    int get_next(string s, int sz)
    {
        int n = s.size();
        int next[n+1];
        int i = 0,j = -1;
        next[0] = -1;
        while(i < n){
            if(j == -1 || s[i] == s[j]){
                ++i;++j;
                next[i] = j;
            }else{
                j = next[j];
            }
        }
        while(next[n] >= sz) next[n] = next[next[n]];//公共部分不能超过size
        return next[n];
    }
};